/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-10-31
 * Time: 23:56
 */

//丢失的数字
public class Demo {
    public int missingNumber(int[] nums) {
        //方法一：把数组0到n下标和原数组的元素异或到一起
        // int ret = 0;
        // for(int x : nums) ret ^= x;
        // for(int i = 0; i <= nums.length; i++) ret ^= i;

        // return ret;


        //方法二：哈希表,把原数组在哈希表一个标记,下次遍历哈希表如果没有标记就返回
        // int n = nums.length;
        // boolean[] hash = new boolean[n+1];
        // for(int i = 0; i < n; i++)
        //     hash[nums[i]] = true;

        // int i;
        // for(i = 0; i <= n; i++)
        //     if(!hash[i]) break;

        // return i;




        //方法三：高斯求和公式(等差数列求和公式)
        int n = nums.length;
        int total = (0 + n) * (n+1) / 2;
        int sum = 0;
        for(int x : nums)
            sum += x;

        return total - sum;
    }
}
